1344B - Monopole Magnets - CodeForces Solution

#include <string>
#include <iomanip>
#include <iostream>
#include <vector>
#include <set>
#include <bitset>
#include <map>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <numeric>
#include <cstring>
#include <complex>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef vector<pii> vii;
typedef set<int> si;
typedef map<int, int> mii;
typedef map<char, int> mci;
typedef complex<double> cd;
 
#define x first
#define y second
#define mp make_pair 
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()

const int INF = 1e9 + 1;
const ll INF_LL = (ll)1e18;
const ll MOD = 1e9 + 7;
// const int MOD = 998244353;
const int ALPHA = 26;
const int MAXN = 2e5 + 200;
const int LOG = 18;
const int SIEVE = (int)1e6 + 10;
const ld EPS = 1e-9;
const ld SCALE = 1e+6;

vector<vb> grid;
vector<vi> color;

int n, m;
int c = 0;
int dirs[2][4] = {
    {1, 0, -1, 0},
    {0, 1, 0, -1}
};

inline bool valid(int x, int y) {
    return x < n && x >= 0 && y < m && y >= 0;
}

void dfs(pii v, int c) {
    color[v.x][v.y] = c;

    for (int i = 0; i < 4; i++) {
        int nx = v.x + dirs[0][i];
        int ny = v.y + dirs[1][i];

        if (valid(nx, ny) && grid[nx][ny] && color[nx][ny] == 0) {
            pii u = {nx, ny};
            dfs(u, c);
        }
    }
}

bool check_black() {
    bool ok = true;
    for (int i = 0; i < n; i++) {
        int colored = color[i][0] > 0;
        for (int j = 1; j < m; j++) {
            if (color[i][j] == color[i][j-1]) continue;
            else if (color[i][j]) colored++;
        }

        if (colored > 1) ok = false;
    }

    for (int j = 0; j < m; j++) {
        int colored = color[0][j] > 0;
        for (int i = 1; i < n; i++) {
            if (color[i][j] == color[i-1][j]) continue;
            else if (color[i][j]) colored++;
        }

        if (colored > 1) ok = false;
    }

    return ok;
}

bool check_white() {
    int unfilled_row = 0;
    int unfilled_col = 0;
    for (int i = 0; i < n; i++)
        unfilled_row += count(all(color[i]), 0) == m;

    for (int j = 0; j < m; j++) {
        int cnt = 0;
        for (int i = 0; i < n; i++)
            if (color[i][j] == 0) cnt++;

        if (cnt == n) unfilled_col++;

    }

    return (unfilled_row > 0 && unfilled_col > 0) || (unfilled_row == 0 && unfilled_col == 0);
}

void solve() {
    cin >> n >> m;
    grid = vector<vb>(n, vb(m));
    color = vector<vi>(n, vi(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char c; cin >> c;
            grid[i][j] = c == '#';
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] && color[i][j] == 0)
                dfs({i, j}, ++c);
        }
    }

    bool ok = check_black() && check_white();
    cout << (ok ? c : -1) << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}